Oct 99 Challenge
Volume Number: 15
Issue Number: 10
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
SuperDuperGhost
This month we're going to play a word game. One derived from a game called GHOST. The
basic concept is simple - players spell a word, taking turns adding letters to the
growing word, trying to avoid being the player who says the last letter of the word.
To start, one player says a letter. The next player thinks of (but does not reveal) a
word that begins with the given letter, and then announces the first two letters of that
word. The next player thinks of a (possibly different) word that starts with the first
two letters, and announces the first three letters of that word. Play continues until a
player spells an entire word that is more than three letters long. The player who
completes the word loses the round. If a player spells a string that is not part of a real
word, that player loses the round.
A game with three players might go like this:
Adam: [thinking of "toast"]: T Betsy: [thinking of "tadpole"]: TA
Cynthia: [thinking of "tatting"]: TAT [which with three letters does
not count as a word] Adam: [now thinking of "tattoo," since "tadpole" no longer
fits the current string of letters]: TATT Betsy: [also thinking of "tattoo"]:
TATTO Cynthia: [has two options: finish the word "tattoo" and lose
this round, or spell a nonexistent word, and also lose. She
resigns]
In our game, there are a few variations. Instead of always adding a letter to the end of
the string, we'll also play games where you can only add to the beginning, games where
you can add to the beginning or to the end, and games where you can add a letter
anywhere. Our games will also be restricted to two players, with each Challenge
contestant competing against each other contestant.
The prototype for the code you should write is:
#if defined(__cplusplus)
typedef enum {
addToEndOnly = 0,
addToBeginningOnly,
addToBeginningOrEnd,
addAnywhere
void InitSuperDuperGhost(
const char *dictWords[],/* alphabetically sorted uppercase
dictionary words */
long numDictionaryWords /* number of null-terminated words in
dictionary */
);
void NewGhostGame(
GameType theGameType
);
void PlayGhost(
const char *ghostString, /* the string so far,
null-terminated */
char newGhostString[256], /* new ghostString, one letter added
to ghostString */
int *wordInMindIndex,
/* your string will match
dictWords[wordInMindIndex] */
int charPositions[256],
/* index into dictWords[wordInMindIndex]
for each char in newGhostString */
);
void TermSuperDuperGhost(void);
#if defined(__cplusplus)
}
#endif
The vocabulary for our game consists of numDictionaryWords alphabetically sorted
uppercase words provided to your InitSuperDuperGhost routine in the dictWords
parameter. The dictionary will typically consist of 40000-50000 words but will
never exceed 100000 words. All dictWords will be greater than 3 letters in length.
InitSuperDuperGhost should analyze the dictionary and create intermediate tables if
appropriate. At the end of the contest, TermSuperDuperGhost will be called, where you
should deallocate any dynamic memory allocated by InitSuperDuperGhost.
Each round will consist of each Challenge entry competing against each other entry in a
game of each GameType, once playing first and once playing second. Each player will be
notified of the start of a new game with a call to NewGhostGame. At each turn, a
player's PlayGhost routine will be called. The null-terminated ghostString parameter
will provide the string played thus far in the game, which is guaranteed to be part of
some word in dictWords. The PlayGhost routine must add a single character to the
ghostString, at the beginning, the end, or anywhere, depending on theGameType
parameter to this game, and return the result in newGhostString. PlayGhost must
return in wordInMindIndex the index into dictWords of the word matched by
newGhostString. To help the test program evaluate your move, you must also set the
charPositions array, so that:
newGhostString[i] =
dictWords[wordInMindIndex][charPositions[i]]
The winner of each game wins 100 points. Each player's score is reduced by 1 point
for each 10 milliseconds of execution time, including the time taken by the
initialization and termination routines. The Challenge winner will be the player with
the most points at the end of the tournament.
If you cannot add a letter to the ghostString without forming a word, you should return
a null string in newGhostString. Alternatively, if you form a word in dictWords but
return a non-null string, you will be penalized 50 points.
Here's how it works: each month we present a new programming challenge.
First, write some code that solves the challenge. Second, optimize your code (a
lot). Then, submit your solution to MacTech Magazine. We choose a winner
based on code correctness, speed, size, and elegance (in that order of
importance) as well as the submission date. In the event of multiple equally
desirable solutions, we'll choose one winner (with honorable mention, but no
prize, given to the runner up). The prize for each month's best solution is a
$100 credit for Developer Depot[TM]. Unless stated otherwise in the problem
statement, the following rules apply: All solutions must be in ANSI compatible
C or C++, or in Pascal. We disqualify entries with any assembly in them
(except for challenges specifically stating otherwise.) You may call any
Macintosh Toolbox routine (e.g., it doesn't matter if you use NewPtr instead of
malloc). We compile all entries into native PowerPC code with compiler
options set to enable all available speed optimizations. The development
environment to be used for selecting the winner will be stated in the problem.
Limit your code to 60 characters per line or compress and binhex the
solution; this helps with e-mail gateways and page layout. We publish the
solution and winners for each month's Programmer's Challenge three months
later. All submissions must be received by the 1st day of the month printed on
the front cover of this issue. You can get a head start on the Challenge by
reading the Programmer's Challenge mailing list. It will be posted to the list
on or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com with the subject "subscribe challenge-A". Mark
solutions "Attn: Programmer's Challenge Solution" and send it by e-mail to
one of the Programmer's Challenge addresses in the "How to Communicate
With Us" section on page 2 of this issue. Include the solution, all related files,
and your contact info. MacTech Magazine reserves the right to publish any
solution entered in the Programmer's Challenge. Authors grant MacTech
Magazine the exclusive right to publish entries without limitation upon
submission of each entry. Authors retain copyrights for the code.
This month's Challenge was suggested by JG Heithcock, who wins 2 Challenge points for
the suggestion. If you have an idea that you think would make a good Challenge problem,
send it to for possible consideration in a future Challenge.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted
this month. Java entries must be accompanied by a test driver that uses the interface
provided in the problem statement.
Three Months Ago Winner
It seemed like a simple Challenge when I wrote it. The July C-to-HTML Challenge, that
is. Write some code to convert a valid C/C++ file into HTML, so that the .html file
displays in Netscape Navigator the same way the .c, .cp, or.h file is displayed by the
CodeWarrior (Pro 4) IDE. A simple matter of syntax coloring, right?
Well, yes, but it wasn't quite that simple. First, there is the question of #pragma and
other preprocessor directives. The list of which directives CodeWarrior recognizes
requires a little research and experimentation. Second, the treatment of #pragmas and
other proprocessor directives is something less than consistent in CodeWarrior Pro 4.
For example, consider the following directives:
#ident
#pragma options align=mac68k
#pragma ANSI_strict
#pragma register_coloring
__declspec(export)
__declspec(import) // notice import is not hilighted
Of that list, "#ident" is recognized but not colored, "options" is colored but
"align=mac68k" is not, "ANSI_strict" (and most other #pragma directives) is
colored, but "register_coloring" (and another set of directives) is not. The "export
argument in a __declspec command is highlighted, but "import" is not. Go figure.
Then there was the question of line continuations. The CodeWarrior IDE doesn't color
an include file as a string when it is written on one line:
... but it does color it if the #include is broken into two lines with a line continuation
character.
And proprocessor directives broken with line continuations are colored based on what
the fragment looks like. In the following examples, "if" is colored in both places, but
the rest of the directive is not. Go figure some more.
#if
def K
#def
ine L
#end
if
Other inputs that tripped some people up:
HTML.h" /* note the unmatched quotes (") here, one is black,
the other gray!*/
long q='//st';
long r='/*..';
long s='..*/';
The proprocessor coloring confusion probably turned off some potential contestants,
but, if that were not enough, there was the issue of proportional fonts. The original
problem statement required that tab characters be processed correctly, including
spacing when using proportional fonts. That turns out to be rather difficult in html,
so, after some discussion on the Challenge mailing list, I decided to test with
monospaced fonts only.
Speaking of the mailing list, if you are not already on it, I would encourage you to join.
Not only does it give you more time to solve the Challenge (problems are sent out on or
around the 12th of the preceding month), but you can also tune in to any problem
clarifications. See <http://www.mactech.com/progchallenge> for subscription
instructions.
So, after that long introduction, congratulations ONCE AGAIN to Ernst Munter (Kanata,
Ontario) for submitting the fastest and most correct solution to the C-to-HTML
Challenge. This is Ernst's third Challenge win in a row - is there no one out there
ready to mount a serious Challenge to his outstanding record?! Ernst and two of the
other participants took advantage of the HTML tag and other Cascading Style
Sheet properties in converting code for display in a browser. Ernst parses the text
using a state machine and six tables, defined in the HTMLcodes structure, based on
whether the state corresponds to leading white space, intervening white space,
preprocessor lines, strings, C-style comments, or C++-style comments. Text
coloring is done using style sheets. Ernst's code converts the familiar "Hello World
program from:
/*
* Hello World for the CodeWarrior
* © 1997-1998 Metrowerks Corp.
*
* Questions and comments to:
*
*
*/